#ifndef __D_MINIMIZE2D_H__
#define __D_MINIMIZE2D_H__

#include "common2d.h"
#include "minimize1d.h"

inline arg	calc_r2d(const test2d& _test_left, const test2d& _test_right, const arg& _m)
{
	return _m * (_test_right.coord[1] - _test_left.coord[1]) + 
		(_test_right.value - _test_left.value) * (_test_right.value - _test_left.value) /
		(_m * (_test_right.coord[1] - _test_left.coord[1])) - 2 * (_test_right.value + _test_left.value);
}

inline arg	calc_coord2d(const test2d& _test_left, const test2d& _test_right, arg& _m)
{
	arg new_arg	= (_test_right.coord[1] + _test_left.coord[1]) / 2 - (_test_right.value - _test_left.value) / (2 * _m);
	if ((new_arg <= _test_left.coord[1]) || (new_arg >= _test_right.coord[1]))
	{
		new_arg	= (_test_right.coord[1] + _test_left.coord[1]) / 2;
	}
	return new_arg;
}

inline void	calc_m2d(const test2d& _test_left, const test2d& _test_right, arg& _m)
{
	arg curr_m	= fabs((_test_right.value - _test_left.value) / (_test_right.coord[1] - _test_left.coord[1]));
	if (curr_m > _m)
	{
		_m	= curr_m;
	}
}

// ---
void	insert_fetch2d(test2d** _tests_array, size& _tests_size, size& _tests_size_max, 
					   test2d* _fetch_array)
{
	test2d* tests_array	= *_tests_array;
	if (_tests_size == _tests_size_max)
	{
		_tests_size_max		*= 2;
		test2d* new_array	= (test2d*)malloc(sizeof(test2d) * _tests_size_max);

		size i	= 0;
		size j	= 0;
		size p	= 0;
		while ((i < _tests_size) && (j < fetch_size2d))
		{
			if (tests_array[i].coord[1] < _fetch_array[j].coord[1])
			{
				new_array[p]	= tests_array[i];
				++i; ++p;
			}
			else
			{
				new_array[p]	= _fetch_array[j];
				++j; ++p;
			}
		}
		while (i < _tests_size)
		{
			new_array[p]	= tests_array[i];
			++i; ++p;
		}
		while (j < fetch_size2d)
		{
			new_array[p]	= _fetch_array[j];
			++j; ++p;
		}

		*_tests_array	= new_array;
		free(tests_array);

		_tests_size	+= fetch_size2d;
	}
	else
	{
		if (_tests_size != 0)
		{
			size p	= _tests_size + fetch_size2d - 1;
			size i	= _tests_size - 1;
			size j	= fetch_size2d - 1;

			while (j >= 0)
			{
				if (tests_array[i].coord[1] > _fetch_array[j].coord[1])
				{
					tests_array[p]	= tests_array[i];
					--i; --p;
				}
				else
				{
					tests_array[p]	= _fetch_array[j];
					--j; --p;
				}
			}
		}
		else
		{
			for (size i = 0; i < fetch_size2d; ++i)
			{
				tests_array[i]	= _fetch_array[i];
			}
		}
		_tests_size	+= fetch_size2d;
	}
}
// ---
void	minimize2d(test_func* _func, args _args, size _argc, args2d _min, args2d _max, args2d _eps)
{
	size tests_size_max	= fetch_size2d;
	size tests_size		= 0;
	test2d*	tests_array	= (test2d*)malloc((sizeof(test2d) * tests_size_max));

	test_func* func	= _func;
	args f_args		= _args;

	arg eps	= _eps[1];

	arg r_array[fetch_size2d];
	size r_index_array[fetch_size2d];

	test2d fetch_array[fetch_size2d];
	arg coord		= _min[1];
	arg delta_coord	= (_max[1] - _min[1]) / (2 * fetch_size2d - 1);
	for (size i = 0; i < fetch_size2d; ++i)
	{
		fetch_array[i].coord[1]	= coord;
		coord	+= delta_coord;
	}
	minimize_fetch1d(func, fetch_array, _args, _argc, _min[0], _max[0], _eps[0]);
	insert_fetch2d(&tests_array, tests_size, tests_size_max, fetch_array);

	for (size i = 0; i < fetch_size2d; ++i)
	{
		fetch_array[i].coord[1]	= coord;
		coord	+= delta_coord;
	}
	minimize_fetch1d(func, fetch_array, _args, _argc, _min[0], _max[0], _eps[0]);
	insert_fetch2d(&tests_array, tests_size, tests_size_max, fetch_array);

	arg prev_min	= 0;
	arg curr_min	= ARG_MAX;
	arg curr_min_coord	= 0;

	arg m	= 1;
	arg t	= 1;

	do 
	{
		for (size i = 0; i < fetch_size2d; ++i)
		{
			r_array[i]	= -ARG_MAX;
		}

		for (size i = 1; i < tests_size; ++i)
		{
			arg r_temp	= calc_r2d(tests_array[i - 1], tests_array[i], m);

			size r_index	= 0;
			for (; r_index < fetch_size2d; ++r_index)
			{
				if (r_temp < r_array[r_index])
				{
					break;
				}
			}
			if (r_index != 0)
			{
				--r_index;
				for (size k = 0; k <= r_index; ++k)
				{
					r_array[k]			= r_array[k + 1];
					r_index_array[k]	= r_index_array[k + 1];
				}
				r_array[r_index]	= r_temp;
				r_index_array[r_index]	= i;
			}
		}
		
		for (size i = 0; i < fetch_size2d; ++i)
		{
			size k			= r_index_array[i];
			fetch_array[i].coord[1]	= calc_coord2d(tests_array[k - 1], tests_array[k], m);
		}

		minimize_fetch1d(func, fetch_array, _args, _argc, _min[0], _max[0], _eps[0]);

		for (size i = 0; i < fetch_size2d; ++i)
		{
			size k			= r_index_array[i];
			calc_m2d(tests_array[k - 1], fetch_array[i], m);
			calc_m2d(fetch_array[i], tests_array[k], m);
		}

		insert_fetch2d(&tests_array, tests_size, tests_size_max, fetch_array);

		prev_min	= curr_min;
		curr_min	= ARG_MAX;
		for (size i = 0; i < fetch_size2d; ++i)
		{
			if (fetch_array[i].value < curr_min)
			{
				curr_min		= fetch_array[i].value;
				curr_min_coord	= fetch_array[i].coord[1];
			}
		}
	}
	while (fabs(curr_min - prev_min) > eps);
}
#endif